package pATT.profilingAlgorithm.PersonalSearcher;
/***************************************************************************
 *                              ValueSortedMap                             * 
 *                       initial version by: Ryan Scherle                  *
 *                      copyright (C) 2000 IGLU Research Group             *
 *                             rscherle@acm.org                            *
 ***************************************************************************/
/***************************************************************************
 * The licence for this code is included in LICENSE.txt.  If you did not   *
 * get this file with this distribution, request a copy from               *
 * iglu@cs.indiana.edu                                                     *
 ***************************************************************************/

import java.util.Map;
import java.util.AbstractMap;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
import java.util.Vector;
import java.util.Iterator;
import java.io.Serializable;

/** 
 * Holds an mapping between objects and their values, ordered by value.
 * This class is similar to <code>SortedMap</code> except
 * the objects are sorted by their values, rather than by the
 * keys themselves.
 * <p>
 * This class is intended for use with objects that receive a
 * value from a complex computation, such as document/query similarity.
 * <p>
 * If you need to sort objects by some method other than an external
 * value, use <code>TreeSet</code> or <code>TreeMap</code>
 * and create a custom <code>Comparator</code>. This class does not implement
 * <code>SortedMap</code> because it does not have an explicit
 * <code>Comparator</code>.
 * <p>
 * <b>Note that this implementation is not synchronized.</b>
 * If multiple threads access a map concurrently, and at least one of
 * the threads modifies the map structurally, it must be synchronized
 * externally. (A structural modification is any operation
 * that adds or deletes one or more mappings; merely changing the value
 * associated with an existing key is not a structural
 * modification.) This is typically accomplished by synchronizing on some
 * object that naturally encapsulates the map. If no
 * such object exists, the map should be "wrapped" using the
 * <code>Collections.synchronizedMap</code> method. This is
 * best done at creation time, to prevent accidental unsynchronized
 * access to the map:
 * <blockquote>
 * <pre>
 * Map m = Collections.synchronizedMap(new ValueSortedMap(...));
 * </pre>
 * </blockquote>
 *
 * <p>This map keeps cached, sorted vectors of the elements in both
 * forward and backward order.  This is to speed up multiple accesses
 * to the iterator functions.
 * <p>
 * 
 * @author <a href="mailto:rscherle@acm.org">Ryan Scherle</a>
 * @author <a href="mailto:trbauer@indiana.edu">Travis Bauer</a>
 * @see iglu.ir.TermVector
 * @see java.util.SortedMap
 * @see java.util.TreeSet
 * @see java.util.TreeMap
 * @version 1.0
 */
@SuppressWarnings("unchecked")
public class ValueSortedMap extends AbstractMap
  implements Serializable, Cloneable
{
  /**
	 * 
	 */
	private static final long serialVersionUID = 1L;
protected HashMap storedItems;
  protected Vector forwardSortedVector = null;
  protected Vector reverseSortedVector = null;

  /**
     An empty map, for use when you don't want to do anthing
     to the vector.
  **/
  public static final ValueSortedMap EMPTY = new ValueSortedMap();

  
  /////////////////////////////////////////////////////////////////
  /** 
   * Constructs an empty map.
   */
  public ValueSortedMap()
  {
    storedItems = new HashMap();
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Constructs a new map from an existing mapping.
   */
public ValueSortedMap(Map map)
  {
    storedItems = new HashMap(map);
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Returns the number of elements in this map.
   */
  public int size()
  {
    return storedItems.size();
  }
  
  /////////////////////////////////////////////////////////////////
  /** 
   * Returns <code>true</code> if this map contains no key-value mappings.
   */
  public boolean isEmpty()
  {
    return storedItems.isEmpty();
  }
  
  /////////////////////////////////////////////////////////////////
  /** 
   * Returns an <b>unordered</b> set of all items in the map.
   * These are <code>Map.entry</code> objects.
   */
  public Set entrySet()
  {
    return storedItems.entrySet();
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Returns true if the specified key is in the mapping.
   */
  public boolean containsKey(Object key)
  {
    return storedItems.containsKey(key);
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Returns the value to which this map maps the specified key. If
   * the key isn't in the map, returns null.
   */
  public Object get(Object key)
  {
    return storedItems.get(key);
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Returns the value to which this map maps the specified key. If
   * the key isn't in the map, or the value isn't a <code>Number</code>,
   * returns 0.
   */
  public double getDouble(Object key)
  {
    double result = 0;
    
    Object keyVal = get(key);
    if((keyVal != null) && (keyVal instanceof Number))
      {
	result = ((Number)keyVal).doubleValue();
      }
    
    return result;
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Adds an item and its value to the map. If the item already
   * exists in the map, the new value replaces the old value.
   */
  public Object put(Object key, Object value)
  {
    clearSorts();
    return storedItems.put(key, value);
  }
  
  /////////////////////////////////////////////////////////////////
  /** 
   * Adds an item and its value to the map. If the item already
   * exists in the map, the new value replaces the old value.
   */
  public Object put(Object key, double value)
  {
    clearSorts();
    return this.put(key,new Double(value));
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Removes the mapping for this key from this map if present.
   * Returns the value previously given to the key.
   */
  public Object remove(Object key)
  {
    clearSorts();
    Object value = this.get(key);
    storedItems.remove(key);

    return value;
  }
  
  /////////////////////////////////////////////////////////////////
  /** 
   * Copies all of the mappings from the specified map
   * to this one.  If an item already exists in the map, the new
   * value replaces the old value.
   */
  public void putAll(Map map)
  {
    clearSorts();
    storedItems.putAll(map);
  }

  /////////////////////////////////////////////////////////////////
  /**
     Truncates this map to the given length. The top
     <code>numItems</code> items, ordered by value, are kept.
  **/
  public void truncateTo(int numItems)
  {
  //  Debug.assert(numItems > 0);
    
    HashSet removeItems = new HashSet();

    Iterator myIt = keyIterator();
    int itemsSeen = 0;
    while(myIt.hasNext() && itemsSeen < numItems)
      {
	myIt.next();
	itemsSeen++;
      }
    while(myIt.hasNext())
      {
	removeItems.add(myIt.next());
      }

    subtract(removeItems);
  }

  /////////////////////////////////////////////////////////////////
  /**
     Performs a set difference on the list of items.
  **/
  public void subtract(Set subItems)
  {
    clearSorts();
    Iterator itemIt = subItems.iterator();
    while(itemIt.hasNext())
      {
	Object theItem = itemIt.next();
	storedItems.remove(theItem);
      }
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Removes all mappings from this map.
   */
  public void clear()
  {
    clearSorts();
    storedItems.clear();
  }

  /////////////////////////////////////////////////////////////////
  /**
     Removes the cached sort vectors in preparation for a change.
  **/
  private void clearSorts()
  {
    forwardSortedVector=null;
    reverseSortedVector=null;
  }
  
  /////////////////////////////////////////////////////////////////
  /** 
   * Returns a set view of the keys contained in this map. These keys
   * aren't ordered, because we've gotten rid of the values that
   * were used to order them.
   */
  public Set keySet()
  {
    return storedItems.keySet();
  }

  /////////////////////////////////////////////////////////////////
  /**
   * Returns an unordered iterator over the set.  Each object
   * returned by the iterator is a Map.entry item.  This function
   * gives you a relatively inexpensive way to iterate over
   * the set when you don't care about the order.  keyIterator()
   * returns items in order, but is relatively computationally
   * expensive.
   */
  public Iterator iterator() {
    return storedItems.entrySet().iterator();
  }

  /////////////////////////////////////////////////////////////////
  /** 
   * Returns an iterator for the keys contained in this map.
   * Only the keys are included in the iterator, but they are ordered
   * by their value. If the value is needed, it can be recalled with
   * the <code>get()</code> or <code>getDouble()</code> methods.
   * This iterator does <b>not</b> support the remove operation, even
   * though it might appear to support it.
   */
  public Iterator keyIterator()
  {
    if (forwardSortedVector!=null) return forwardSortedVector.iterator();
    Iterator storedIt = storedItems.entrySet().iterator();
    TreeSet sortedSet = new TreeSet();
    forwardSortedVector = new Vector();

    // store all items in a TreeSet to sort them
    while(storedIt.hasNext())
      {
	Map.Entry thisItem = (Map.Entry)storedIt.next();
	sortedSet.add(new ObjectValuePair(thisItem.getKey(),((Double)thisItem.getValue()).doubleValue()));
      }

    // read sorted items, and place the ordered keys in a vector
    Iterator treeIt = sortedSet.iterator();
    while(treeIt.hasNext())
      {
	ObjectValuePair thisPair = (ObjectValuePair)treeIt.next();
	forwardSortedVector.add(thisPair.getObject());
      }
    
    return forwardSortedVector.iterator();
  }

  /////////////////////////////////////////////////////////////////
  /** Returns an iterator over the objects in reverse key order.
   * The objects will be returned in an other the opposite of keyIterator()
   * This iterator does <b>not</b> support the remove operation, even
   * though it might appear to support it.
   */
  public Iterator reverseKeyIterator() {
    if (reverseSortedVector!=null) return reverseSortedVector.iterator();
    Iterator storedIt = storedItems.entrySet().iterator();
    TreeSet sortedSet = new TreeSet();
    reverseSortedVector = new Vector();

    // store all items in a TreeSet to sort them
    while(storedIt.hasNext())
      {
	Map.Entry thisItem = (Map.Entry)storedIt.next();
	sortedSet.add(new ObjectValuePair(thisItem.getKey(),((Double)thisItem.getValue()).doubleValue()));
	}

    // remove items, and place the ordered keys in a vector
    Iterator treeIt = sortedSet.iterator();
    while(treeIt.hasNext())
      {
	ObjectValuePair thisPair = (ObjectValuePair)treeIt.next();
	reverseSortedVector.insertElementAt(thisPair.getObject(), 0);
      }
    
    return reverseSortedVector.iterator();
  }    


  /////////////////////////////////////////////////////////////////
  /** 
   * Returns a string representation of this map.
   */
  public String toString()
  {
    String result = "[";

    Iterator allEntries = keyIterator();
    while(allEntries.hasNext())
      {
	Object thisItem = allEntries.next();
	result += "<" + thisItem + "," + get(thisItem) + ">";
	if (allEntries.hasNext())
	  result += ",";
      }

    result += "]";

    return result;
  }

  /////////////////////////////////////////////////////////////////
  /**
   * Normalizes the values in the map, so that its length (as a vector)
   * is 1. It is assumed that every item is mapped to a <code>Number</code>.
   * If this is not true, only the items that map to a <code>Number</code>
   * will be nomalized. Everything else will have its value set to zero.
   */
  public void normalizeSquare()
  {
    // find the vector's length
    double squaredWeightSum = 0.0;
    Iterator allEntries = keyIterator();
    while(allEntries.hasNext())
      {
	Object thisItem = allEntries.next();
	squaredWeightSum += getDouble(thisItem) * getDouble(thisItem);
      }
    double vectorLength = Math.sqrt(squaredWeightSum);

    // for each mapping, divide the value by the vector length
    allEntries = keyIterator();
    while(allEntries.hasNext())
      {
	Object thisItem = allEntries.next();
	put(thisItem, getDouble(thisItem) / vectorLength);
      }
  }

  public void normalizeAugmented()
  {
    // find the vector's length
    Iterator allEntries = keyIterator();
    double may = getDouble(allEntries.next());
    while(allEntries.hasNext())
      {
	Object thisItem = allEntries.next();
	if (getDouble(thisItem)>may)
		may = getDouble(thisItem);
      }

    // for each mapping, divide the value by the vector length
    allEntries = keyIterator();
    while(allEntries.hasNext())
      {
	Object thisItem = allEntries.next();
	double w = 0.5 + 0.5 * (getDouble(thisItem) / may);
	put(thisItem, w);
      }
  }

  /////////////////////////////////////////////////////////////////
  /**
   * Scales all terms of the map by the given value.  It is assumed
   * that every item is mapped to a <code>Number</code>.
   * If this is not true, only the items that map to a <code>Number</code>
   * will be scaled. Everything else will have its value set to zero.
   */
  public void scaleBy(double n)
  {
    Iterator itemIt = keyIterator();
//    Number thisValue = null;
    
    while(itemIt.hasNext())
      {
	Object thisItem = itemIt.next();
	put(thisItem, getDouble(thisItem) * n);
      }
  }
  
  /////////////////////////////////////////////////////////////////
  /** 
   * Linearly scales the values in the map. After scaling, the lowest
   * value will be 1, the second-lowest will be 2, etc.
   */
  public void linearlyScale()
  {
    int currScore = storedItems.size();
    Iterator itemIt = keyIterator();
    
    while(itemIt.hasNext())
      {
	Object thisItem = itemIt.next();
	put(thisItem, currScore);
	currScore--;
      }
  }
  
  /////////////////////////////////////////////////////////////////
  /**
   * Returns the ordered position of this key in the map.  Returns
   * -1 if the key is not in the map.
   */
  public int rankOrder(Object key) {
    if (!containsKey(key)) return -1;
    int count=0;
    for (Iterator i=keyIterator(); i.hasNext(); ) {
        count++;
        if (i.next().equals(key)) return count;
    }
//    Debug.assert(false);  //should never reach this line
    return -1;
   }

  /////////////////////////////////////////////////////////////////
  /**
   * Creates a shallow clone of the object.  The objects contained
   * in the Map are not themselves cloned.
   */
  public Object clone() {
    return new ValueSortedMap(this);
  }
}



